package com.heima.leetcode.datastructure.linkedlist;

/**
 * 根据值删除节点
 */

public class RemoveElementsByValue {

    /**
     * <h3>方法一</h3>
     * 根据值删除链表中的节点（复数）
     *
     * @param head  要删掉的链表的头节点
     * @param value 要删掉的节点的值
     * @return 删除过后的链表的头节点
     */
    public static ListNode removeByValue(ListNode head, int value) {
        ListNode sentinel = new ListNode(-1, head); // 自己创建一个哨兵节点，删除的代码会简洁一些，删除需要找到前一个结点以及要删除的节点
        ListNode p1 = sentinel;
        ListNode p2 = head;
        while (p2 != null) {
            if (p2.val == value) {
                // 删掉这个节点
                p1.next = p2.next;
            } else {
                // p1往后移动一位
                p1 = p1.next;
            }
            // p2往后移动一位
            p2 = p2.next;
        }
        return sentinel.next;
    }

    /**
     * <h3>方法二，递的时候，找到最后一个节点，归的时候如果当前归的节点的值等于要删除的值，则返回上一次归算的头节点，否则将这一次归的节点作为头节点返回</h3>
     * 用递归实现根据值删除链表中的节点（复数）
     * @param head 旧链表的头节点
     * @param value 待删除的节点的值
     * @return 新链表的头节点
     */
    public static ListNode removeByValueRecursion(ListNode head, int value) {
        if (head == null) {
            return null;
        }
        ListNode newHead = removeByValueRecursion(head.next, value);
        if (head.val == value) {
            return newHead;
        }
        head.next = newHead;
        return head;
    }
}
